package fag.core.geometry;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Stack;

/**
 * Classe des polygones 2D. Le polygone est défini par un liste de sommet. Le dernier étant connecté au premier.
 * @author lumz
 */
public class Polygon2D extends AbstractPolygon implements Serializable {
	
	private static final long serialVersionUID = 3016565458103117916L;
	
	private Rectangle2D bounds = new Rectangle2D();
	private List<Vector2D> vertices = new ArrayList<Vector2D>();
	
	/**
	 * Constructeur avec initialisation.
	 * @param vertices Les sommets du polygone.
	 */
	public Polygon2D(List<Vector2D> vertices) {
		set(vertices);
	}
	
	@Override
	public Polygon2D clone() {
		
		Polygon2D clone = (Polygon2D) super.clone();
		
		clone.bounds = bounds.clone();
		clone.vertices = new ArrayList<Vector2D>(vertices.size());
		
		for(Vector2D vertex : vertices)
			clone.vertices.add(vertex.clone());
		
		return clone;
	}
	
	@Override
	public boolean equals(Object other) {
		
		if(this == other)
			return true;
		
		if(!(other instanceof Polygon2D))
			return false;
		
		final Polygon2D polygon = (Polygon2D)(other);
		final int size = vertices.size();
		
		if(size != polygon.vertices.size())
			return false;
		
		for(int i = 0; i < size; ++i)
			if(!vertices.get(i).equals(polygon.vertices.get(i)))
				return false;
		
		return true;
	}
	
	@Override
	public Rectangle2D getBounds() {
		return bounds.clone();
	}
	
	/**
	 * Getter des sommets du polygone.
	 * Attention : Tout changement sur les attributs de cette liste modifiera directement les points du polygone
	 * Attention : Si modification prévu , appelez la methode updateBounds() pour garder à jour la Hitbox
	 * @return Une liste des sommets du polygone.
	 */
	public List<Vector2D> getVertices() {
		// TODO : COPIE DEFENSIVE ? corriger le bug de l'éditeur.
		return vertices;
	}

	/**
	 * Setter des sommets du polygone.
	 * @param vertices La liste des nouveaux sommets du polygone.
	 */
	public void set(List<Vector2D> vertices) {
		
		assert(vertices.size() > 3);
		
		for(Vector2D vertex : vertices)
			this.vertices.add(vertex.clone());
		
		updateBounds();
	}
	
	/**
	 * Assistance pour l'algorithme de détection GJK et EPA. Doit renvoyer le sommet le plus éloigné
	 * sur le vecteur d'assistance.
	 * @param d Le vecteur d'assistance.
	 * @return Le sommet le plus éloigné sur le vecteur d'assistance.
	 */
	public Vector2D supportVertex(Vector2D d) {
		
		Vector2D result = new Vector2D();
		
		if(vertices.size() > 0) {
			
			result = vertices.get(0);
			double max = d.dot(result);
			
			for(int i = 1; i < vertices.size(); ++i) {
				
				Vector2D candidate = vertices.get(i);
				
				if(d.dot(candidate) > max) {
					max = d.dot(candidate);
					result = candidate;
				}
			}
		}
		
		return result.clone();
	}
	
	@Override
	public String toString() {
		
		String result = new String() + "Polygon2D(";
		
		for(int i = 0; i < vertices.size(); ++i) {
			
			if(i > 0)
				result += "; ";
			
			Vector2D vertex = vertices.get(i);
			result += vertex.getX() + ", " + vertex.getY();
		}
		
		return result;
	}
	
	/**
	 * Précalcule le volume englobant du polygone.
	 */
	protected void updateBounds() {
		
		double minX = 0;
		double minY = 0;
		double maxX = 0;
		double maxY = 0;
		
		// Initialisation avec le premier sommet du polygone
		if(vertices.size() > 0) {
			Vector2D initialVertex = vertices.get(0);
			minX = initialVertex.getX();
			minY = initialVertex.getY();
			maxX = minX;
			maxY = minY;
		}
		
		// Elargissement aux sommets du polygone
		for(Vector2D vertex : vertices) {
			
			if(minX > vertex.getX())
				minX = vertex.getX();
			
			if(maxX < vertex.getX())
				maxX = vertex.getX();
			
			if(minY > vertex.getY())
				minY = vertex.getY();
		
			if(maxY < vertex.getY())
				maxY = vertex.getY();
			
		}
		
		bounds.set(minX, minY, maxX - minX, maxY - minY);
	}
	
	/**
	 * Obtenir une instance de Polygon2D à partir d'un nuage de points.
	 * @param polygon Le nuage de points.
	 * @return L'enveloppe convexe du nuage de points.
	 */
	
	public static Polygon2D getConvexHull(List<Vector2D> polygon) {
        int min = 0;
        int length = polygon.size();
        
        /* On cherche le vector2D d'ordonnée minimale */
        for (int i = 1; i < length; i++) 
        {
            Vector2D get = polygon.get(i);
            if (get.getY() < polygon.get(min).getY())
                min = i;
            else 
            {
                if (get.getY() == polygon.get(min).getY())
                {
                    if (get.getX() < polygon.get(min).getX())
                        min = i;
                }
            }
        }
        
        // Déclaration du pivot de l'enveloppe convexe (on va tourner autour de ce vector2D)
        final Vector2D pivot = polygon.get(min);
        ArrayList<Vector2D> sorted = new ArrayList<Vector2D>(polygon);
        
        // Tri polaire des points
        Collections.sort(sorted, new Comparator<Vector2D>() {
            public int compare(Vector2D o1, Vector2D o2) {      	
                if (o1.equals(o2)) {
                    return 0;
                }
                if (pivot.angle(o1,o2)) {
                    return 1;
                } else {
                    return -1;
                }
            }
        });
        sorted.add(0, pivot);
        
        // Pile de traitement de l'EC.
        Stack<Vector2D> stack = new Stack<Vector2D>();
        stack.push(sorted.get(length - 1));
        stack.push(pivot);
        int i = 1;
        // Gestion de la pile, on empile et dépile en fonction du déterminant (à gauche/droite)
        while (i < length) {
            Vector2D pt1 = stack.pop();
            Vector2D pt2 = stack.peek();
            Vector2D pt1pt2 = pt1.sub(pt2);
            Vector2D getIpt2 = sorted.get(i).sub(pt2);
            stack.push(pt1);
            if (pt1pt2.isLeftTurn(getIpt2)) {
                stack.push(sorted.get(i));
                i++;
            } else {
                stack.pop();
            }
        }
        
        // Création de l'EC
        ArrayList<Vector2D> convex = new ArrayList<Vector2D>();
        while (!stack.isEmpty()) {
            convex.add(stack.pop());
        }
        convex.remove(convex.size() - 1);
        
        //On retourne EC
        return new Polygon2D(convex);
    }
}
